package personal.parser;

import java.util.*;

public class SimpleGrammar implements Grammar {

    @Override
    public Symbol getStartSymbol() {
        return this.startSymbol;
    }


    @Override
    public Set<Terminal> getTerminals() {
        return this.terminals;
    }


    @Override
    public Set<NonTerminal> getNonTerminals() {
        return this.nonTerminals;
    }


    @Override
    public List<Production> getProductions() {
        return productions;
    }


    @Override
    public Symbol getSymbol(String expression) {
        return symbolsByExpression.get(expression);
    }

    @Override
    public Set<Terminal> fist(Symbol... symbols) {
        if (Arrays.stream(symbols).anyMatch(this::isIllegalSymbol)) throw new UnknownError("非法符号");
//        for (Symbol symbol : symbols) if (this.isIllegalSymbol(symbol)) throw new UnknownError("非法符号");
        if (symbols.length == 1) return this.getFirstBySymbol(symbols[0]); // 单个符号：FIRST(X)
        Set<Terminal> ret = new HashSet<>();
        for (Symbol symbol : symbols) {
            if (symbol == Grammar.EMPTY) continue;
            ret.addAll(this.getFirstBySymbol(symbol)); // 显然是没有 ε 的
            break; // 直接退出即可
        }

        return ret;
    }

    /**
     * @param symbol 指定符号
     * @return 指定符号不是当前文法的合法符号
     */
    private boolean isIllegalSymbol(Symbol symbol) {
        if (symbol instanceof Terminal) {
            return symbol != Grammar.EMPTY && !this.getTerminals().contains((Terminal) symbol);
        } else if (symbol instanceof NonTerminal) {
            return !this.getNonTerminals().contains((NonTerminal) symbol);
        }
        // 判断异常情况
        throw new UnknownError("既不是终结符，也不是非终结符");
    }


    /**
     * 开始符号
     */
    private final Symbol startSymbol;

    /**
     * 终结符
     */
    private final Set<Terminal> terminals;

    /**
     * 非终结符
     */
    private final Set<NonTerminal> nonTerminals;

    /**
     * 产生式
     */
    private final List<Production> productions;

    /**
     * 通过字符串形式获得 Symbol
     */
    private final Map<String, Symbol> symbolsByExpression;

    /**
     * 单符号的 first 集
     */
    private final Map<Symbol, Set<Terminal>> firstOfSymbol;

    private Set<Terminal> getFirstBySymbol(Symbol symbol) {
        return this.firstOfSymbol.get(symbol);
    }

    /**
     * 初始化单符号的 first 集
     */
    private void initFirstBySymbol() {
        if (this.getTerminals().contains(Grammar.EMPTY)) throw new IllegalArgumentException("禁止出现空串");
        // 先处理终结符的 first 集
        for (Terminal terminal : this.getTerminals()) {
            this.firstOfSymbol.putIfAbsent(terminal, new HashSet<>(List.of(terminal)));
        }
        // 再处理非终结符的 first 集
        // 转移影响，右部的非终结符将影响左部
        Map<NonTerminal, Set<NonTerminal>> bucket = new HashMap<>();
        for (Production production : this.getProductions()) {
            try {
                NonTerminal right = (NonTerminal) production.rightSide().get(0);
                bucket.putIfAbsent(right, new HashSet<>());
                bucket.get(right).add(production.leftSide());
            } catch (ClassCastException ignored) {
            }
        }
        // 先将各非终结符的 first 集初始化为空集
        for (NonTerminal nonTerminal : this.getNonTerminals()) {
            this.firstOfSymbol.putIfAbsent(nonTerminal, new HashSet<>());
        }
        // 循环流程
        Queue<NonTerminal> qeBuffer = new LinkedList<>(this.getNonTerminals()); // 更新队列
        // 初始化更新队列，先处理右部是终结符开头的
        for (Production production : this.getProductions()) {
            try {
                Terminal right = (Terminal) production.rightSide().get(0);
                this.firstOfSymbol.get(production.leftSide()).add(right);
                qeBuffer.add(production.leftSide()); // 放入更新队列
            } catch (ClassCastException ignored) {
            }
        }
        while (!qeBuffer.isEmpty()) {
            NonTerminal u = qeBuffer.poll(); // 当前非终结符
            try {
                for (NonTerminal v : bucket.get(u)) {
                    if (this.firstOfSymbol.get(v).addAll(this.firstOfSymbol.get(u))) { // first 集发生改变
                        qeBuffer.add(v);
                    }
                }
            } catch (NullPointerException ignored) { // 说明这个非终结符并不影响任何其它的
            }
        }
    }

    /**
     * 构造函数，传入以字符串形式给出的：开始符号，非终结符集合、终结符集合、产生式、以及产生式的分隔符。
     * 我们要求显示地传入终结符集合和非终结符集合的原因是：避免由产生式拼写错误导致初始化错误的文法。
     *
     * @param startSymbolExpression        开始符号
     * @param nonTerminalSymbolExpressions 非终结符集合
     * @param terminalSymbolExpressions    终结符集合
     * @param delimiterExpression          分隔符，理解成对字符串形式的产生式调用 String.split
     * @param productionExpressions        产生式列表
     */
    public SimpleGrammar(String startSymbolExpression, List<String> nonTerminalSymbolExpressions, List<String> terminalSymbolExpressions, String delimiterExpression, String... productionExpressions) {
        // 初始化
        this.nonTerminals = new HashSet<>();
        this.terminals = new HashSet<>();
        this.productions = new ArrayList<>();
        this.symbolsByExpression = new HashMap<>();
        this.firstOfSymbol = new HashMap<>();
        // 初始化非终结符集合、终结符集合，并检查冲突
        for (String expression : nonTerminalSymbolExpressions) { // 非终结符
            NonTerminal symbol = new NonTerminal(expression);
            if (this.symbolsByExpression.putIfAbsent(expression, symbol) != null) // 不是第一次出现
                throw new IllegalArgumentException("符号冲突：" + expression);
            this.nonTerminals.add(symbol);
        }
        for (String expression : terminalSymbolExpressions) { // 终结符
            Terminal symbol = new Terminal(expression);
            if (this.symbolsByExpression.putIfAbsent(expression, symbol) != null) // 不是第一次出现
                throw new IllegalArgumentException("符号冲突：" + expression);
            this.terminals.add(symbol);
        }
        this.startSymbol = this.getSymbol(startSymbolExpression);
        // 初始化产生式
        for (String productionExpression : productionExpressions) { // 遍历产生式
            // split
            String[] expressionList = productionExpression.split(delimiterExpression);
            if (expressionList.length < 2) { // 保证有一个左部，一个右部
                throw new IllegalArgumentException(String.format("产生式 %s 长度过短", productionExpression));
            }
            // 检查左部
            Symbol leftSide = this.getSymbol(expressionList[0]);
            if (leftSide == null) {
                throw new IllegalArgumentException(String.format("产生式 %s 的左部是未知符号", productionExpression));
            }
            if (!(leftSide instanceof NonTerminal)) {
                throw new IllegalArgumentException(String.format("产生式 %s 的左部不是非终结符", productionExpression));
            }
            // 检查右部
            List<Symbol> rightSide = new ArrayList<>();
            for (int i = 1; i < expressionList.length; ++i) {
                Symbol rightSideSymbol = this.getSymbol(expressionList[i]);
                if (rightSideSymbol == null) {
                    throw new IllegalArgumentException(String.format("产生式 %s 的右部出现未知符号 %s", productionExpression, expressionList[i]));
                }
                rightSide.add(rightSideSymbol);
            }
            // 创建产生式
            this.productions.add(new Production((NonTerminal) leftSide, rightSide));
        }
        // 初始化单符号的 first 集
        this.initFirstBySymbol();
    }


    @Override
    public String toString() {
        StringBuilder ret = new StringBuilder();
        ret.append(String.format("开始符号：%s\n", this.startSymbol));
        for (Grammar.Production production : this.productions)
            ret.append(production).append("\n");
        ret.append(String.format("终结符：%s\n", this.terminals));
        ret.append(String.format("非终结符：%s\n", this.nonTerminals));
        return ret.toString();
    }
}
